home *** CD-ROM | disk | FTP | other *** search
/ The Ultimate Window Set -…Games & Quality Programs / The Ultimate Window Set - 250 Games & Quality Programs.iso / win / pro30 / bitops.c next >
Text File  |  1987-09-22  |  13KB  |  439 lines
  1.  
  2. /* BITOPS.C - Various bit-manipulation procedures.
  3.  *
  4.  *    Audit Trail
  5.  *
  6.  *    09/11/87 - v001 - GSK - Original
  7.  */
  8.  
  9. #include "ctype.h"
  10.  
  11. #define FULLBYT 0xff
  12. #define TBUFSIZ 100
  13. #define SUCCESS    0
  14. #define FAILURE    -1
  15. #define NULL (char *)0
  16.  
  17. typedef unsigned BOOL;
  18.  
  19. /* *************************** GENERAL NOTES *****************************
  20.  *
  21.  *    Most of these routines deal with "bit fields" of arbitrary
  22.  *    length. In general, you pass them a (char) pointer to a block of memory,
  23.  *     which will be interpreted and manipulated as a stream of bits, regardless
  24.  *    of byte or word boundaries after the original pointer. Several of these 
  25.  *    routines take a bit offset argument, which is an ABSOLUTE number of bits
  26.  *    (zero-relative) from the base pointer; in other words, a bit offset of
  27.  *    75 points to the 76th bit in the block, starting from the base pointer.
  28.  *
  29.  ****************************************************************************/
  30.  
  31.  
  32. /* GETBIT - Get the value of the bit (0, 1) at passed ptr, offset by bitoffs
  33.  *            bits. The offset may be any positive number; if >8, the byte 
  34.  *            pointer will be incremented accordingly.
  35.  */
  36.  
  37. short getbit(ptr, bitoffs)
  38.  
  39. char *ptr;        /* Base pointer */
  40. short bitoffs;    /* Offset from ptr in number of bits */
  41.  
  42. {
  43.  
  44.     if (ptr == NULL || bitoffs < 0)
  45.         return (FAILURE);
  46.  
  47.     ptr += (bitoffs / 8);    /* Knock up ptr to byte requested */
  48.     bitoffs %= 8;        /* Get bit relative to its own byte */
  49.  
  50.     return (short)((*ptr >> (7 - bitoffs)) & 1);
  51. }
  52.  
  53.  
  54. /* SETBIT - Set a specified bit number in a char string to 1 or 0. The bit
  55.  *            number may be any positive value; if > 8, the byte pointer will
  56.  *            be incremented accordingly.
  57.  */
  58.  
  59. short setbit(ptr, bitnum, val)
  60.  
  61. char *ptr;        /* Base of string */
  62. short bitnum;    /* Bit number, 0 relative */
  63. short val;        /* Value to set, 1 or 0 */
  64.  
  65. {
  66.     short byteoffs;        /* Byte offset in string */
  67.     char mask;        /* Masking value */
  68.  
  69.  
  70.     if (ptr == NULL || bitnum < 0 || (val != 0 && val != 1))
  71.         return (FAILURE);
  72.  
  73.     ptr += (byteoffs = bitnum / 8);    /* Calc offset, reset ptr */
  74.  
  75.     if (byteoffs)
  76.         bitnum %= (byteoffs * 8);    /* Find bit within byte */
  77.  
  78. /* Mask = bit string of zeroes with one in bitnum position */
  79.  
  80.      mask = 1 << (7 - bitnum);
  81.  
  82.     if (val)            /* If turn-on bit, OR with mask */
  83.         *ptr |= mask;
  84.     else                /* Else, AND with inverse (ones-complement) of mask */
  85.         *ptr &= ~mask;
  86.  
  87.     return (SUCCESS);
  88. }
  89.  
  90.  
  91. /* COUNTBIT - Count the bits of specified value (0 or 1) in a bit field. The
  92.  *                field may be any number of bytes in length. If val==0, then
  93.  *                "off" bits will be counted; otherwise, "on" bits.
  94.  */
  95.  
  96. short countbit(basep, nbytes, val)
  97.  
  98. char *basep;    /* Starting byte to begin count */
  99. short nbytes;    /* Number of bytes to count thru */
  100. short val;        /* Bit value to count, 0 or 1 */
  101.  
  102. {
  103.     short count;    /* Number of bits counted */
  104.     short bit;    /* Bit loop counter */
  105.     char *ptr;    /* Loop pointer */
  106.  
  107.  
  108.     if (basep == NULL || nbytes <= 0 || (val != 0 && val != 1))
  109.         return (FAILURE);
  110.  
  111.     count = 0;
  112.  
  113.     for (ptr = basep; ptr < basep + nbytes; ptr++)
  114.         {
  115.         for (bit = 0; bit < 8; bit++)
  116.         count += (getbit(ptr, bit) == val);
  117.         }
  118.  
  119.     return (count);
  120. }
  121.  
  122.  
  123. /* BITPATRN -  Generate an array of chars or ints corresponding to the bit
  124.  *                pattern of the passed char. If patyp == 'C', an array of
  125.  *                character '0's and '1's will be generated; if 'I', an array
  126.  *                numeric 0/1's.
  127.  *
  128.  *            NOTE that you pass a single CHAR, not a char *. Thus if you
  129.  *                need a pattern array more than 8 elements long, call
  130.  *                bitpatrn() in a loop and concatenate the results.
  131.  */
  132.  
  133. short bitpatrn(chr, patp, patyp)
  134.  
  135. char chr;    /* Char to generate pattern from */
  136. char *patp;    /* Ptr to array of chars or ints, depending on patyp */
  137. char patyp;    /* Pattern type: Char or Int (NOT case sensitive) */
  138.  
  139. {
  140.     short ptrinc;    /* Pointer increment per bit */
  141.     short bit;        /* Bit counter */
  142.     short bitval;    /* Bit value, 1 or 0 */
  143.  
  144.  
  145.     patyp = toupper(patyp);
  146.  
  147.     if (patp == NULL || (patyp != 'C' && patyp != 'I'))
  148.         return (FAILURE);
  149.  
  150.     ptrinc = 1 + (patyp == 'I');
  151.  
  152.     for (bit = 0; bit < 8; bit++, patp += ptrinc)
  153.         {
  154.         bitval = getbit(&chr, bit);
  155.  
  156.         if (patyp == 'I')    /* Int array: Set low bytes of each pair */
  157.             {
  158.             *patp = bitval;
  159.             *(patp + 1) = 0;
  160.             }
  161.         else
  162.             *patp = '0' + bitval;
  163.         }
  164.     return (SUCCESS);
  165. }
  166.  
  167.  
  168. /* BYTE2BIT -  Translate the byte passed to a bit pattern, placed at char
  169.  *                *ptr, offset by bitoffs bits from left. Do not write onto next
  170.  *                byte from ptr if lastbyt set. This allows a bit pattern to be
  171.  *                copied to another place in memory regardless of byte
  172.  *                boundaries. For example, if bitoffs == 3, then the left 5 bits
  173.  *                of the passed byte will be copied to the right 5 bits of the
  174.  *                destination ptr, and the right 3 bits of the byte onto the
  175.  *                left 3 bits of the following location (unless lastbyt == YES),
  176.  *                in which case only the FIRST dest char will be written on).
  177.  *                Issuing a call with a ZERO bit offset, like:
  178.  *
  179.  *                    byte2bit('A', dest, 0, anything);
  180.  *
  181.  *                is equivalent to: *dest = 'A';
  182.  */
  183.  
  184. short byte2bit(byte, ptr, bitoffs, lastbyt)
  185.  
  186. char byte;        /* Character to translate */
  187. char *ptr;        /* DESTINATION Ptr: Points to starting byte to write to */
  188. short bitoffs;    /* Offset of starting bit from DESTINATION ptr, 0-7 */
  189. BOOL lastbyt;    /* Flag: Do not write bits to next char if set */
  190.  
  191. {
  192.     short bit;    /* Bit counter */
  193.  
  194.  
  195.     if (ptr == NULL || bitoffs < 0 || bitoffs > 7)
  196.         return (FAILURE);
  197.  
  198. /* Write left side of passed byte to right side of 1st destination char, 
  199.    leaving left side of dest char unchanged */
  200.  
  201.     for (bit = bitoffs; bit <= 7; bit++)
  202.         setbit(ptr, bit, getbit(&byte, bit - bitoffs));
  203.  
  204. /* Write right side of byte to left side of next destination char, 
  205.    leaving right side unchanged */
  206.  
  207.     if (bitoffs && !lastbyt)
  208.         for (bit = 0; bit < bitoffs; bit++)
  209.             setbit(ptr + 1, bit, getbit(&byte, bit + 8 - bitoffs));
  210.  
  211.     return (SUCCESS);
  212. }
  213.  
  214.  
  215. /* BIT2BYTE.C - Take next 8 bits from starting char *, offset by specified
  216.  *                number of bits (bitoffs), translate to a byte and return
  217.  *                value as a char. Starting point need not conform to a byte
  218.  *                boundary. For example, if bitoffs = 3, then translation will
  219.  *                begin with the 4th bit (offsets are 0-relative) of the passed
  220.  *                ptr; if lastbyt == YES, then only the remaining 5 bits will
  221.  *                be translated (offsets 3 thru 7); otherwise, a full 8 bits
  222.  *                will be translated, the remaining 3 coming from the left 3
  223.  *                bits of the byte following ptr. Issuing a call with a ZERO
  224.  *                bit offset like:
  225.  *
  226.  *                    mychar = bit2byte(there, 0, anything);
  227.  *
  228.  *                is equivalent to: mychar = *there;
  229.  */
  230.  
  231. char bit2byte(ptr, bitoffs, lastbyt)
  232.  
  233. char *ptr;        /* Ptr to starting byte to take from */
  234. short bitoffs;    /* Offset of starting bit from ptr, 0-7 */
  235. BOOL lastbyt;    /* Flag: Do not take bits from next char if set */
  236.  
  237. {
  238.     char byte;
  239.  
  240.  
  241.     if (ptr == NULL || bitoffs < 0 || bitoffs > 7)
  242.         return (0);
  243.  
  244.     byte = *ptr << bitoffs;        /* Set left side of byte */
  245.  
  246.     if (bitoffs && !lastbyt)    /* Set right side from next byte */
  247.  
  248.         byte |= (*(++ptr) >> (8 - bitoffs));
  249.  
  250.     return (byte);
  251. }
  252.  
  253.  
  254. /* INSBITS - Insert specified number of bits to bit field beginning at basep,
  255.  *                starting insertion bitoffs bits from the base. Inserted bits
  256.  *                will be all of the same    value (0 or 1). Bits above the
  257.  *                insertion point will be pushed up in memory, up the limit of
  258.  *                total field size fldsize (arbitrary size limit defined by
  259.  *                TBUFSIZ).
  260.  *
  261.  *            NOTE: If you need a routine to insert a specific bit pattern
  262.  *                (not just all 0's or 1's), use this as a template. You only
  263.  *                need to change the "fill middle bytes" section.
  264.  */
  265.  
  266. short insbits(basep, bitoffs, nbits, val, fldsize)
  267.  
  268. char *basep;    /* Ptr to base of bit field */
  269. short bitoffs;    /* Number of bits offset from left to begin insert */
  270. short nbits;    /* Number of bits to insert */
  271. short val;        /* Value to insert, 1 or 0 */
  272. short fldsize;    /* Total size of bit field in bytes */
  273.  
  274. {
  275.     char buffer[TBUFSIZ];        /* Temporary copy buffer */
  276.     char *firstbyt, *lastbyt;    /* Bytes where insert begins/ends */
  277.     short firstoffs, lastoffs;    /* Bit offsets in first, last bytes */
  278.     short n;                    /* Field index counter */
  279.     short lastbit;                /* Offset of last bit in field */
  280.     char *ptr;                    /* Temporary ptr */
  281.  
  282.  
  283.     if (basep == NULL || nbits <= 0 || fldsize <= 0 || fldsize > TBUFSIZ)
  284.         return (FAILURE);
  285.  
  286.     firstbyt = basep + bitoffs / 8;
  287.     lastbit = bitoffs + nbits - 1;
  288.     lastbyt = basep + lastbit / 8;
  289.     firstoffs = bitoffs % 8;
  290.     lastoffs = lastbit % 8;
  291.  
  292.     if (firstbyt >= basep + fldsize)
  293.         return (FAILURE);
  294.  
  295.     setmem(buffer, sizeof(buffer), 0);    /* Init copy buffer */
  296.  
  297. /* Copy from firstbyt thru end of field to buffer */
  298.  
  299.     for (ptr = firstbyt, n = 0; ptr < basep + fldsize; ptr++, n++)
  300.         buffer[n] = bit2byte(ptr, firstoffs, ptr == basep + fldsize - 1);
  301.  
  302. /* Set the starting byte, leaving left part as is */
  303.  
  304.     if (val)
  305.         *firstbyt |= FULLBYT >> firstoffs;
  306.     else
  307.         *firstbyt &= FULLBYT << (8 - firstoffs);
  308.  
  309. /* Fill middle bytes; do not overwrite end of field */
  310.  
  311.     for (ptr = firstbyt + 1; ptr < lastbyt; ptr++)
  312.         {
  313.         if (ptr >= basep + fldsize)
  314.             break;
  315.  
  316.         *ptr = (val) ? FULLBYT : 0;
  317.         }
  318.  
  319. /* Set ending byte, leaving right part as is */
  320.  
  321.     if (lastbyt < basep + fldsize && lastbyt != firstbyt)
  322.         {
  323.         if (val)
  324.             *lastbyt |= FULLBYT << (7 - lastoffs);
  325.         else
  326.             *lastbyt &= FULLBYT >> (lastoffs + 1);
  327.         }
  328.  
  329. /* Write buffer from last byte to end of field */
  330.  
  331.     for (ptr = lastbyt, n = 0; ptr < basep + fldsize; ptr++, n++)
  332.         byte2bit(buffer[n], ptr, lastoffs + 1, ptr == basep + fldsize - 1);
  333.  
  334.     return (SUCCESS);
  335. }
  336.  
  337.  
  338. /* DELBITS.C - Delete specified number of bits from bit field beginning at
  339.  *                basep offset by bitoffs bits. The bit field may be any number
  340.  *                of bytes in length, and the deleted section may be any number
  341.  *                of bits in length and need not conform to byte boundaries. The
  342.  *                bits above the deleted section are moved down to fill the
  343.  *                gap, and the top of the field filled with the specified value.
  344.  *
  345.  *        NOTE: Bit field size fldsize is arbitrarily limited to TBUFSIZ as
  346.  *                defined below.
  347.  */
  348.  
  349. short delbits(basep, bitoffs, nbits, val, fldsize)
  350.  
  351. char *basep;    /* Ptr to base of bit field */
  352. short bitoffs;    /* Number of bits offset from left to begin delete */
  353. short nbits;    /* Number of bits to delete */
  354. short val;        /* Value to fill vacated right side of field, 1 or 0 */
  355. short fldsize;    /* Total size of bit field in BYTES */
  356.  
  357. {
  358.     char buffer[TBUFSIZ];        /* Temporary copy buffer */
  359.     char *firstbyt, *lastbyt;    /* Bytes where delete begins/ends */
  360.     short firstoffs, lastoffs;    /* Bit offsets in first, last bytes */
  361.     short n;                    /* Field index counter */
  362.     short lastbit;                /* Offset of last bit in field */
  363.     char *ptr;                    /* Temporary ptr */
  364.  
  365.  
  366.     if (basep == NULL || nbits <= 0 || fldsize <= 0 || fldsize > TBUFSIZ)
  367.         return (FAILURE);
  368.  
  369.     firstbyt = basep + bitoffs / 8;
  370.     lastbit = bitoffs + nbits - 1;
  371.     lastbyt = basep + lastbit / 8;
  372.     firstoffs = bitoffs % 8;
  373.     lastoffs = lastbit % 8;
  374.  
  375.     if (firstbyt >= basep + fldsize)
  376.         return (FAILURE);
  377.  
  378.     if (val)
  379.         setmem(buffer, sizeof(buffer), FULLBYT);    /* Init copy buffer */
  380.     else
  381.         setmem(buffer, sizeof(buffer), 0);
  382.  
  383. /* Copy to buffer: From bit after end of deleted section to end of field */
  384.  
  385.     if (++lastoffs > 7)
  386.         {
  387.         lastbyt++;
  388.         lastoffs = 0;
  389.         }
  390.  
  391.     for (ptr = lastbyt, n = 0; ptr < basep + fldsize; ptr++, n++)
  392.         buffer[n] = bit2byte(ptr, lastoffs, ptr == basep + fldsize - 1);
  393.  
  394. /* Write buffer to deleted part thru end of field; end is filled with val */
  395.  
  396.     for (ptr = firstbyt, n = 0; ptr < basep + fldsize; ptr++, n++)
  397.         byte2bit(buffer[n], ptr, firstoffs, ptr == basep + fldsize - 1);
  398.  
  399.     return (SUCCESS);
  400. }
  401.  
  402.  
  403. /* BITZVALU - Evaluate the next nbits bits from the starting char * and bit
  404.  *                offset and return the value. Uses a simple counting algorithm,
  405.  *                starting with the rightmost bit in the designated field and
  406.  *                moving left, adding a successive power of 2 for each "on" bit.
  407.  *
  408.  *            EXAMPLES: Given a pointer to the array of hex values: 1E A4 7C
  409.  *
  410.  *                        bitzvalu(ptr, 8, 8)        returns 164 (00A4)
  411.  *                        bitzvalu(ptr, 3, 4)        returns  15 (000F)
  412.  *                        bitzvalu(ptr, 10, 10)    returns 583 (0247)
  413.  *
  414.  *        NOTE: Returns an unsigned value. The number of bits evaluated may not
  415.  *              be more than 16. If bad parameters are passed, returns 0.
  416.  */
  417.  
  418. unsigned bitzvalu(ptr, bitoffs, nbits)
  419.  
  420. char *ptr;        /* Ptr to starting byte to take from */
  421. short bitoffs;    /* Offset of starting bit from ptr */
  422. short nbits;    /* Number of bits to evaluate */
  423. {
  424.     unsigned num = 0;    /* Initialize all bits to 0 */
  425.     int bit;
  426.     unsigned mult = 1;
  427.  
  428.     if (ptr == NULL || nbits < 1 || nbits > 16)
  429.         return (0);
  430.  
  431.     for (bit = nbits - 1; bit >= 0; bit--, mult *= 2)
  432.         num += (getbit(ptr, bitoffs + bit) * mult);
  433.  
  434.     return (num);
  435. }
  436.  
  437.  
  438. /* CONTRIBUTED BY: Gordon Kramer, Liberty Tree Software, Belchertown, MA */
  439.